/*
 *                        _oo0oo_
 *                       o8888888o
 *                       88" . "88
 *                       (| -_- |)
 *                       0\  =  /0
 *                     ___/`---'\___
 *                   .' \\|     |// '.
 *                  / \\|||  :  |||// \
 *                 / _||||| -:- |||||- \
 *                |   | \\\  - /// |   |
 *                | \_|  ''\---/''  |_/ |
 *                \  .-\__  '-'  ___/-. /
 *              ___'. .'  /--.--\  `. .'___
 *           ."" '<  `.___\_<|>_/___.' >' "".
 *          | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 *          \  \ `_.   \_ __\ /__ _/   .-` /  /
 *      =====`-.____`.___ \_____/___.-`___.-'=====
 *                        `=---='
 * 
 * 
 *      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 * 
 *            佛祖保佑       永不宕机     永无BUG
 * 
 *        佛曰:  
 *                写字楼里写字间，写字间里程序员；  
 *                程序人员写程序，又拿程序换酒钱。  
 *                酒醒只在网上坐，酒醉还来网下眠；  
 *                酒醉酒醒日复日，网上网下年复年。  
 *                但愿老死电脑间，不愿鞠躬老板前；  
 *                奔驰宝马贵者趣，公交自行程序员。  
 *                别人笑我忒疯癫，我笑自己命太贱；  
 *                不见满街漂亮妹，哪个归得程序员？
 * 
 * @Author       : Inky
 * @Date         : 2020-06-07 15:16:05
 * @LastEditTime : 2020-06-08 16:16:25
 * @FilePath     : /inky-ws/src/计算思维与操作系统/实验三/binaryTree.c
 * @Description  : 
 */

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ERROR 0
#define OK 1
#define MAX_SIZE 20

typedef struct node {
    int data;
    struct node * left, * right;
}Node, *BinTree;

int InitBinTree(BinTree tree){
    tree->data = 0;
    tree->left = NULL;
    tree->right = NULL;
    return OK;
}

int PreOrder(BinTree tree, int (*Visit)(Node *)){
    if (NULL != tree) {
        if (Visit(tree))
            if (PreOrder(tree->left, Visit))
                if (PreOrder(tree->right, Visit))
                    return OK;
        return ERROR;
    }
    return OK;
}

int FreeNode(Node * node){
    if(NULL!=node){
        free(node);
        node = NULL;
    }
    return OK;
}

int InOrder(BinTree tree, int(*Visit)(Node *)){
    if (NULL != tree) {
        if (InOrder(tree->left, Visit))
            if (Visit(tree))
                if (InOrder(tree->right, Visit))
                    return OK;
        return ERROR;
    }
    return OK;
}

int PostOrder(BinTree tree, int(*Visit)(Node *)){
    if (NULL != tree) {
        if (PostOrder(tree->left, Visit))
            if (PostOrder(tree->right, Visit))
                if (Visit(tree))
                    return OK;
        return ERROR;
    }
    return OK;
}

int DestroyTree(BinTree tree){
    return PostOrder(tree, FreeNode);
}

Node * InputNode(){
    Node * node = (BinTree)malloc(sizeof(Node));
    if(NULL==node){
        return ERROR;
    }
    InitBinTree(node);
    scanf("%d", &node->data);
    return node;
}

int Print(Node * node){
    if(NULL!=node){
        printf("%d\t", node->data);
    }
    return OK;
}

static int layer = 1;
int PrintTree(BinTree tree) {
    static int i = 0;
    Node* queue[MAX_SIZE] = { NULL };
    queue[i++] = tree;
    // i++;
    for (int j = 0; j < MAX_SIZE; j++) {
        if (NULL != queue[j]) {
            queue[i++] = queue[j]->left;
            queue[i++] = queue[j]->right;
            // printf("%d\t", queue[j]->data);
        }
        else {
            if (j >= 19 || queue[j + 1] == NULL) {
                break;
            }
        }
    }
    for (int j = 0; j < i; j++) {
        if (queue[j] != NULL)
            printf("%d\t", queue[j]->data);
        else
            printf("NaN\t");
        if (j == pow(2, layer) - 2) {
            printf("\n");
            layer++;
        }
    }
    return OK;
}

static int min = 0x7fffffff;
static int max = 0;
static int count = 0;

int DMaxMin(Node * node){
    //static int depth = 0;
    if(NULL!=node){
        // count++;
        if(max < node->data){
            max = node->data;
        }
        if(min > node->data){
            min = node->data;
        }
    }
    return OK;
}
int main(){
    BinTree tree = (BinTree)malloc(sizeof(Node));
    Node * p;
    InitBinTree(tree);
    tree->data = 7; // 7
    
    p = InputNode();   
    tree->left = p;//1

    p = InputNode();
    tree->right = p;//2
    
    p = InputNode();
    tree->right->left = p;//3

    p = InputNode();
    tree->right->right = p;//4
    
    p = InputNode();
    tree->left->right = p;//5

    p = InputNode();
    tree->right->left->right = p;//6

    puts("\n\n");
    PrintTree(tree);
    puts("\n");
    printf("preOrder print:\n");
    PreOrder(tree, Print);
    printf("\nInOrder print : \n");
    InOrder(tree, Print);
    printf("\nPostOrder print:\n");
    PostOrder(tree, Print);

    PreOrder(tree, DMaxMin);
    int deepth = log(count) / log(2) + 1;
    printf("\nSize : %d,\t Deepth : %d,\t Max : %d,\t Min : %d\n", count, layer, max, min);

    DestroyTree(tree);

    return 0;
}